{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Programmable Robot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: robot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #机器人大冒险"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>力扣团队买了一个可编程机器人，机器人初始位置在原点<code>(0, 0)</code>。小伙伴事先给机器人输入一串指令<code>command</code>，机器人就会<strong>无限循环</strong>这条指令的步骤进行移动。指令有两种：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>U</code>: 向<code>y</code>轴正方向移动一格</li>\n",
    "\t<li><code>R</code>: 向<code>x</code>轴正方向移动一格。</li>\n",
    "</ol>\n",
    "\n",
    "<p>不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用<code>obstacles</code>表示。机器人一旦碰到障碍物就会被<strong>损毁</strong>。</p>\n",
    "\n",
    "<p>给定终点坐标<code>(x, y)</code>，返回机器人能否<strong>完好</strong>地到达终点。如果能，返回<code>true</code>；否则返回<code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>command = &quot;URR&quot;, obstacles = [], x = 3, y = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>U(0, 1) -&gt; R(1, 1) -&gt; R(2, 1) -&gt; U(2, 2) -&gt; R(3, 2)。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>command = &quot;URR&quot;, obstacles = [[2, 2]], x = 3, y = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>机器人在到达终点前会碰到(2, 2)的障碍物。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>command = &quot;URR&quot;, obstacles = [[4, 2]], x = 3, y = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>到达终点后，再碰到障碍物也不影响返回结果。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>2 &lt;= command的长度 &lt;= 1000</code></li>\n",
    "\t<li><code>command</code>由<code>U，R</code>构成，且至少有一个<code>U</code>，至少有一个<code>R</code></li>\n",
    "\t<li><code>0 &lt;= x &lt;= 1e9, 0 &lt;= y &lt;= 1e9</code></li>\n",
    "\t<li><code>0 &lt;= obstacles的长度 &lt;= 1000</code></li>\n",
    "\t<li><code>obstacles[i]</code>不为原点或者终点</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [programmable-robot](https://leetcode.cn/problems/programmable-robot/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [programmable-robot](https://leetcode.cn/problems/programmable-robot/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"URR\"\\n[]\\n3\\n2', '\"URR\"\\n[[2, 2]]\\n3\\n2', '\"URR\"\\n[[4, 2]]\\n3\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        a, b = 0, 0\n",
    "        locus = [[0,0]]\n",
    "        for i in command:\n",
    "            if i == 'U':\n",
    "                a += 1\n",
    "            else:\n",
    "                b += 1\n",
    "            locus.append([b, a])\n",
    "        # 假设一定能到达终点\n",
    "        circle = min(x//b, y//a)\n",
    "        if [x-b*circle, y-a*circle] not in locus:\n",
    "            return False\n",
    "        for o in obstacles:\n",
    "            i, j = o[0], o[1]\n",
    "            # 如果当前节点在目标节点右上方，直接跳过\n",
    "            if i>x or j>y:\n",
    "                continue\n",
    "            c = min(i//b, j//a)\n",
    "            if [i-b*c, j-a*c] in locus:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx, yy = 0, 0\n",
    "        dot_list = [[0, 0]]\n",
    "        for i in command:\n",
    "            if i == 'R':\n",
    "                xx += 1\n",
    "            else:\n",
    "                yy += 1\n",
    "            dot_list.append([xx, yy])\n",
    "        xb = dot_list[-1][0]\n",
    "        yb = dot_list[-1][1]\n",
    "        for i in obstacles:\n",
    "            if i[0] > x or i[1] >y:\n",
    "                continue\n",
    "            b = min(i[0] // xb, i[1] // yb)\n",
    "            if [i[0] - b * xb, i[1] - b * yb] in dot_list:\n",
    "                return False\n",
    "        b = min(x // xb, y // yb)\n",
    "        if [x - b * xb, y - b *yb] in dot_list:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        temp=[0,0]\n",
    "        one_cycle=[[0,0]]\n",
    "        for elem in command:\n",
    "            if elem=='U':\n",
    "                temp[1]=temp[1]+1\n",
    "                one_cycle.append(temp[:])\n",
    "            else:\n",
    "                temp[0]=temp[0]+1\n",
    "                one_cycle.append(temp[:])\n",
    "        for elem in obstacles:\n",
    "            if (elem[0]>=x )and elem[1]>=y:\n",
    "                continue\n",
    "            all_cycle=min(elem[0]//temp[0],elem[1]//temp[1])\n",
    "            leave=[0,0]\n",
    "            leave[0]=elem[0]-all_cycle*temp[0]\n",
    "            leave[1]=elem[1]-all_cycle*temp[1]\n",
    "            if leave in one_cycle:\n",
    "                return False\n",
    "        all_cycle=min(x//temp[0],y//temp[1])\n",
    "        leave=[0,0]\n",
    "        leave[0]=x-all_cycle*temp[0]\n",
    "        leave[1]=y-all_cycle*temp[1]\n",
    "        if leave in one_cycle:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        # if x<0 or y<0:return False\n",
    "        # # obs=defaultdict(defaultdict(int))\n",
    "        # obs=defaultdict(list)\n",
    "        # for i,j in obstacles:\n",
    "        #     # obs[i][j]=1\n",
    "        #     obs[i].append(j)\n",
    "        # i,j=0,0\n",
    "        # for step in range(x+y):\n",
    "        #     if command[step%len(command)]=='U':\n",
    "        #         j+=1\n",
    "        #     elif command[step%len(command)]=='R':\n",
    "        #         i+=1\n",
    "        #     else:\n",
    "        #         continue\n",
    "        #     print(i,j)\n",
    "        #     if j in obs[i]:return False\n",
    "        #     # if [i,j] in obstacles:return False\n",
    "        #     # if obs[i][j]==1:return False\n",
    "        #     if i==x and j==y:return True\n",
    "        # return False\n",
    "        xi,yi=0,0\n",
    "        # first_circle=[]#这里还要一个【0,0】\n",
    "        first_circle=[[0,0]]\n",
    "        for c in command:\n",
    "            if c=='U':yi+=1\n",
    "            if c=='R':xi+=1\n",
    "            first_circle.append([xi,yi])#第一个循环里所有经过的轨迹\n",
    "        loops=min(x//xi,y//yi)\n",
    "        if [x-loops*xi,y-loops*yi]not in first_circle:return False\n",
    "        #判断障碍物\n",
    "        for obx,oby in obstacles:\n",
    "            loops=min(obx//xi,oby//yi)\n",
    "            if obx<=x and oby<=y and [obx-loops*xi,oby-loops*yi]in first_circle:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        route = self.getRoute(command)\n",
    "        if not self.onRoute(route, [x, y]):\n",
    "            return False\n",
    "        for obstacle in obstacles:\n",
    "            if (obstacle[0] >= x and obstacle[1] >= y) or (obstacle[0] == x and obstacle[1] == y):\n",
    "                continue\n",
    "            if self.onRoute(route, obstacle):\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def onRoute(self, route: List[List[int]], pos: List[int]) -> bool:\n",
    "        dists = route[-1]\n",
    "        cycle = min(pos[0] // dists[0], pos[1] // dists[1])\n",
    "        location = [dists[0] * cycle, dists[1] * cycle]\n",
    "        if location[0] == pos[0] and location[1] == pos[1]:\n",
    "            return True\n",
    "        for point in route:\n",
    "            xx = location[0] + point[0]\n",
    "            yy = location[1] + point[1]\n",
    "            if xx == pos[0] and yy == pos[1]:\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "    def getRoute(self, command: str) -> List[List[int]]:\n",
    "        route = []\n",
    "        x, y = 0, 0\n",
    "        for cmd in command:\n",
    "            if cmd == 'U':\n",
    "                y += 1\n",
    "            elif cmd == 'R':\n",
    "                x += 1\n",
    "            route.append([x, y])\n",
    "        return route\n",
    "        \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        if x==0 and y==0:\n",
    "            return True\n",
    "    \n",
    "        path = set([(0,0)])\n",
    "        i, j = 0, 0\n",
    "        for c in command:\n",
    "            if c == 'U':\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            path.add((i,j))\n",
    "\n",
    "        def div(x:int, y:int) -> Tuple[int, int]:\n",
    "            m = min(x//i, y//j)\n",
    "            return (x-i*m, y-j*m)\n",
    "        \n",
    "        #print(path)\n",
    "        if div(x,y) not in path:\n",
    "            return False\n",
    "\n",
    "        for a, b in obstacles:\n",
    "            if a>x or b>y:\n",
    "                continue\n",
    "            if div(a, b) in path:\n",
    "                #print(a,b)\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "#RRU\n",
    "#0,0 1,0, 2,0, 2,1\n",
    "#    3,1, 4,1, 4,2\n",
    "#    5,2, 6,2, 6,3\n",
    "\n",
    "#RRUUU\n",
    "#0,0 1,0, 2,0, 2,1, 2,2, 2,3\n",
    "#    3,3, 4,3, 4,4, 4,5, 4,6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        a, b = 0, 0\n",
    "        for s in command:\n",
    "            if s == 'U': b += 1\n",
    "            if s == 'R': a += 1\n",
    "        kk = []\n",
    "        for i, obstacle in enumerate(obstacles):\n",
    "            if obstacle[0] > x or obstacle[1] > y: continue\n",
    "            temp = min(obstacle[0] // a, obstacle[1] // b)\n",
    "            if [obstacle[0] - temp * a, obstacle[1] - temp * b] == [0, 0]:\n",
    "                kk.append([a, b])\n",
    "            else:\n",
    "                kk.append([obstacle[0] - temp * a, obstacle[1] - temp * b])\n",
    "        \n",
    "        min_circle = min(x // a, y // b)\n",
    "        x, y = x - min_circle * a, y - min_circle * b\n",
    "        ans = [0, 0]\n",
    "        flag = 0\n",
    "        for s in command:\n",
    "            if ans == [x, y]:\n",
    "                if min_circle == 0: return True\n",
    "                else: flag = 1\n",
    "            if s == 'U': ans[1] = 1 + ans[1]\n",
    "            elif s == 'R': ans[0] = 1 + ans[0]\n",
    "            if ans in kk: return False\n",
    "        if flag == 1: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "判断会在多少步经过某一点\n",
    "'''\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        \n",
    "        n = len(command)\n",
    "        uPre = [0] * (n + 1)\n",
    "        rPre = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            uPre[i+1] = uPre[i]\n",
    "            rPre[i+1] = rPre[i]\n",
    "\n",
    "            if command[i] == \"U\":\n",
    "                uPre[i+1] += 1\n",
    "                lastU = i\n",
    "            else:\n",
    "                rPre[i+1] += 1\n",
    "                lastR = i\n",
    "\n",
    "        def isVisit(x, y):\n",
    "            #需要达到x, 需要完整走过rdX轮，还要走resX步\n",
    "            rdX = x // rPre[-1]\n",
    "            if rdX * rPre[-1] == x:\n",
    "                #刚好完整走过\n",
    "                rdX = rdX - 1\n",
    "                resX = lastR + 1   #lastR为在command中最后出现的位置，对应rPre需要+1\n",
    "            else:    \n",
    "                resX = rPre.index(x - rdX * rPre[-1])\n",
    "\n",
    "            #需要达到y, 需要完整走过rdY轮，还要走resY步\n",
    "            udY = y // uPre[-1]\n",
    "            if udY * uPre[-1] == y:\n",
    "                udY -= 1\n",
    "                resY = lastU + 1\n",
    "            else:    \n",
    "                resY = uPre.index(y - udY * uPre[-1])\n",
    "\n",
    "            had = [(rdX, resX), (udY, resY)]\n",
    " \n",
    "            had.sort(key = lambda x : (-x[0], -x[1]))\n",
    "\n",
    "            xx = had[0][0] * rPre[-1] + rPre[had[0][1]]\n",
    "            yy = had[0][0] * uPre[-1] + uPre[had[0][1]]\n",
    "\n",
    "\n",
    "            if (xx, yy) == (x, y):\n",
    "                return had[0]\n",
    "            return False\n",
    "\n",
    "\n",
    "        tar = isVisit(x, y)\n",
    "        #print(tar)\n",
    "        if tar == False:\n",
    "            return False\n",
    "        for x, y in obstacles:\n",
    "            temp = isVisit(x, y)\n",
    "            if temp == False:\n",
    "                continue\n",
    "            if temp <= tar:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        def if_arrive(target):    \n",
    "            c = [0, 0]\n",
    "            iter_num1 = target[0] // moves[-1][0]\n",
    "            iter_num2 = target[1] // moves[-1][1]\n",
    "            if iter_num1 <= iter_num2:\n",
    "                iter_num = iter_num1\n",
    "                index = 0\n",
    "            else:\n",
    "                iter_num = iter_num2\n",
    "                index = 1\n",
    "            c[index] = target[index] % moves[-1][index]\n",
    "            c[1 - index] = target[1 - index] - (iter_num * moves[-1][1 - index])\n",
    "            c[1 - index] - c[1 - index] if c[1 - index] > 0 else 0\n",
    "            if c in moves and target[0] <= x and target[1] <= y:\n",
    "                return False\n",
    "            return True\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "        moves = [[0, 0]]\n",
    "        for move in command:\n",
    "            if move == 'U':\n",
    "                yi += 1\n",
    "            else:\n",
    "                xi += 1\n",
    "            if [xi, yi] in obstacles:\n",
    "                return False\n",
    "            moves.append([xi, yi])\n",
    "        for obstacle in obstacles:\n",
    "            if not if_arrive(obstacle):\n",
    "                return False\n",
    "        if if_arrive([x, y]):\n",
    "            return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        if x==0 and y==0:\n",
    "            return True\n",
    "    \n",
    "        path = []\n",
    "        i, j = 0, 0\n",
    "        for c in command:\n",
    "            if c == 'U':\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            path.append((i,j))\n",
    "\n",
    "        def check(a:int, b:int, x:int, y:int) -> bool:\n",
    "            da, db = x-a, y-b\n",
    "            if da < 0 or db < 0:\n",
    "                return False\n",
    "            if (da%i != 0) or (db%j != 0):\n",
    "                return False\n",
    "            return da//i == db//j\n",
    "        \n",
    "        #print(path)\n",
    "        if not any([check(a, b, x, y) for a,b in path]):\n",
    "            return False\n",
    "\n",
    "        for a, b in obstacles:\n",
    "            if a>x or b>y:\n",
    "                continue\n",
    "            if any([check(pa, pb, a, b) for pa, pb in path]):\n",
    "                #print(a,b)\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "#RRU\n",
    "#0,0 1,0, 2,0, 2,1\n",
    "#    3,1, 4,1, 4,2\n",
    "#    5,2, 6,2, 6,3\n",
    "\n",
    "#RRUUU\n",
    "#0,0 1,0, 2,0, 2,1, 2,2, 2,3\n",
    "#    3,3, 4,3, 4,4, 4,5, 4,6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        a=b= 0\n",
    "        # 计算第一次执行完command后, 走过的所有坐标,直接进集合\n",
    "        s = set([(0, 0)])\n",
    "        for c in command:\n",
    "            if c == 'R' :a+= 1\n",
    "            else:b+= 1\n",
    "            s.add((a,b))\n",
    "        c = min(x // a, y // b)\n",
    "        if (x-a * c, y-b* c) not in s:return False\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for ax, ay  in obstacles:\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            c = min(ax // a, ay// b)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ax <= x and ay <= y and (ax - a* c, ay - b * c) in s:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx, yy = 0, 0\n",
    "        dot_list = [[0, 0]]\n",
    "        for i in command:\n",
    "            if i == 'R':\n",
    "                xx += 1\n",
    "            else:\n",
    "                yy += 1\n",
    "            dot_list.append([xx, yy])\n",
    "        xb = dot_list[-1][0]\n",
    "        yb = dot_list[-1][1]\n",
    "        b = min(x // xb, y // yb)\n",
    "        if [x - b * xb, y - b * yb] not in dot_list:\n",
    "            return False\n",
    "        else:\n",
    "            for i in obstacles:\n",
    "                if i[0] > x or i[1] >y:\n",
    "                    continue\n",
    "                b = min(i[0] // xb, i[1] // yb)\n",
    "                if [i[0] - b * xb, i[1] - b * yb] in dot_list:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx, yy = 0, 0\n",
    "        dot_list = [[0, 0]]\n",
    "        for i in command:\n",
    "            if i == 'R':\n",
    "                xx += 1\n",
    "            else:\n",
    "                yy += 1\n",
    "            dot_list.append([xx, yy])\n",
    "        xb = dot_list[-1][0]\n",
    "        yb = dot_list[-1][1]\n",
    "        for i in obstacles:\n",
    "            if i[0] > x or i[1] >y:\n",
    "                continue\n",
    "            b = min(i[0] // xb, i[1] // yb)\n",
    "            if [i[0] - b * xb, i[1] - b * yb] in dot_list:\n",
    "                return False\n",
    "        b = min(x // xb, y // yb)\n",
    "        if [x - b * xb, y - b *yb] in dot_list:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx = yy = 0\n",
    "        trace = {(0, 0)}\n",
    "        for c in command:\n",
    "            xx += 1 if c == 'R' else 0\n",
    "            yy += 1 if c == 'U' else 0\n",
    "            trace.add((xx, yy))\n",
    "        circle = min(x//xx, y//yy)\n",
    "        if (x-circle*xx, y-circle*yy) not in trace:\n",
    "            return False\n",
    "        for o_x, o_y in obstacles:\n",
    "            if o_x > x or o_y > y:\n",
    "                continue\n",
    "            circle = min(o_x//xx, o_y//yy)\n",
    "            if (o_x-circle*xx, o_y-circle*yy) in trace:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        rotue = []\n",
    "        rotue.append([0,0])\n",
    "        x_c,y_c = 0,0\n",
    "        for c in command:\n",
    "            if c==\"R\":\n",
    "                x_c += 1\n",
    "                rotue.append([x_c,y_c])\n",
    "            else:\n",
    "                y_c += 1\n",
    "                rotue.append([x_c,y_c])    \n",
    "\n",
    "        def yu(x1,y1):\n",
    "            cntx,cnty = x1//x_c,y1//y_c\n",
    "            #循环次数\n",
    "            cnt = min(cntx,cnty)\n",
    "            #剩余需要判断是否在一个循环路径里面\n",
    "            yu_x,yu_y = x1-cnt*x_c,y1-cnt*y_c\n",
    "            return [yu_x,yu_y]\n",
    "        if yu(x,y) not in rotue:\n",
    "            return False\n",
    "        for obs in obstacles:\n",
    "            ox,oy = obs[0],obs[1]\n",
    "            if ox<=x and oy<=y and yu(ox,oy) in rotue:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n",
    "        \"\"\"\n",
    "      暴力超时\n",
    "      \"\"\"\n",
    "    #   locx,locy = 0,0\n",
    "    #   while locx<=x and locy<=y:\n",
    "    #     for i in range(len(command)):\n",
    "    #       if command[i]==\"U\":\n",
    "    #         locy += 1\n",
    "    #       if command[i]==\"R\":\n",
    "    #         locx +=1\n",
    "    #       if [locx,locy] in obstacles:\n",
    "    #         return False\n",
    "    #       if locx==x and locy==y:\n",
    "    #         return True\n",
    "    #   return False\n",
    "   \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        i = j = 0\n",
    "        for step in command:\n",
    "            if step == 'U':\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        def arrive(dx,dy):\n",
    "            loop = (dx+dy)//len(command)\n",
    "            res = (dx+dy)%len(command)\n",
    "            step_i = i * loop\n",
    "            step_j = j * loop\n",
    "            if res != 0:\n",
    "                for step in command[0:res]:\n",
    "                    if step == 'U':\n",
    "                        step_j += 1\n",
    "                    else:\n",
    "                        step_i += 1\n",
    "            if step_i == dx and step_j == dy:\n",
    "                return True\n",
    "        if not arrive(x,y):\n",
    "            return False\n",
    "\n",
    "        for dx,dy in obstacles:\n",
    "            if dx + dy >= x + y:\n",
    "                continue\n",
    "            if arrive(dx,dy):\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        a=b= 0\n",
    "        # 计算第一次执行完command后, 走过的所有坐标,直接进集合\n",
    "        s = set([(0, 0)])\n",
    "        for c in command:\n",
    "            if c == 'R' :a+= 1\n",
    "            else:b+= 1\n",
    "            s.add((a,b))\n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // a, y // b)\n",
    "        if (x-a * circle, y-b* circle) not in s:return False\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for ax, ay  in obstacles:\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            c = min(ax // a, ay// b)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ax <= x and ay <= y and (ax - a* c, ay - b * c) in s:\n",
    "                return False \n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx, yy = 0, 0\n",
    "        dot_list = [[0, 0]]\n",
    "        for i in command:\n",
    "            if i == 'R':\n",
    "                xx += 1\n",
    "            else:\n",
    "                yy += 1\n",
    "            dot_list.append([xx, yy])\n",
    "        xb = dot_list[-1][0]\n",
    "        yb = dot_list[-1][1]\n",
    "        b = min(x // xb, y // yb)\n",
    "        if [x - b * xb, y - b * yb] not in dot_list:\n",
    "            return False\n",
    "        else:\n",
    "            for i in obstacles:\n",
    "                if i[0] > x or i[1] >y:\n",
    "                    continue\n",
    "                b = min(i[0] // xb, i[1] // yb)\n",
    "                if [i[0] - b * xb, i[1] - b * yb] in dot_list:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "判断会在多少步经过某一点\n",
    "'''\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        \n",
    "        n = len(command)\n",
    "        uPre = [0] * (n + 1)\n",
    "        rPre = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            uPre[i+1] = uPre[i]\n",
    "            rPre[i+1] = rPre[i]\n",
    "\n",
    "            if command[i] == \"U\":\n",
    "                uPre[i+1] += 1\n",
    "                lastU = i\n",
    "            else:\n",
    "                rPre[i+1] += 1\n",
    "                lastR = i\n",
    "\n",
    "        def isVisit(x, y):\n",
    "            #需要达到x, 需要完整走过rdX轮，还要走resX步\n",
    "            rdX = x // rPre[-1]\n",
    "            if rdX * rPre[-1] == x:\n",
    "                #刚好完整走过\n",
    "                rdX = rdX - 1\n",
    "                resX = lastR + 1\n",
    "            else:    \n",
    "                resX = rPre.index(x - rdX * rPre[-1])\n",
    "\n",
    "            #需要达到y, 需要完整走过rdY轮，还要走resY步\n",
    "            udY = y // uPre[-1]\n",
    "            if udY * uPre[-1] == y:\n",
    "                udY -= 1\n",
    "                resY = lastU + 1\n",
    "            else:    \n",
    "                resY = uPre.index(y - udY * uPre[-1])\n",
    "\n",
    "            had = [(rdX, resX), (udY, resY)]\n",
    "            #print(had)\n",
    "            had.sort(key = lambda x : (-x[0], -x[1]))\n",
    "\n",
    "            xx = had[0][0] * rPre[-1] + rPre[had[0][1]]\n",
    "            yy = had[0][0] * uPre[-1] + uPre[had[0][1]]\n",
    "\n",
    "            #print(had)\n",
    "\n",
    "            if (xx, yy) == (x, y):\n",
    "                return had[0]\n",
    "            return False\n",
    "\n",
    "\n",
    "        tar = isVisit(x, y)\n",
    "        #print(tar)\n",
    "        if tar == False:\n",
    "            return False\n",
    "        for x, y in obstacles:\n",
    "            temp = isVisit(x, y)\n",
    "            if temp == False:\n",
    "                continue\n",
    "            if temp <= tar:\n",
    "                return False\n",
    "\n",
    "\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        a, b = 0, 0\n",
    "        locus = [[0,0]]\n",
    "        for i in command:\n",
    "            if i == 'U':\n",
    "                a += 1\n",
    "            else:\n",
    "                b += 1\n",
    "            locus.append([b, a])\n",
    "        # 假设一定能到达终点\n",
    "        circle = min(x//b, y//a)\n",
    "        if [x-b*circle, y-a*circle] not in locus:\n",
    "            return False\n",
    "        for o in obstacles:\n",
    "            i, j = o[0], o[1]\n",
    "            if i>x or j>y:\n",
    "                continue\n",
    "            c = min(i//b, j//a)\n",
    "            if [i-b*c, j-a*c] in locus:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx, yy = 0, 0\n",
    "        dot_list = [[0, 0]]\n",
    "        for i in command:\n",
    "            if i == 'R':\n",
    "                xx += 1\n",
    "            else:\n",
    "                yy += 1\n",
    "            dot_list.append([xx, yy])\n",
    "        xb = dot_list[-1][0]\n",
    "        yb = dot_list[-1][1]\n",
    "        for i in obstacles:\n",
    "            if i[0] > x or i[1] >y:\n",
    "                continue\n",
    "            b = min(i[0] // xb, i[1] // yb)\n",
    "            if [i[0] - b * xb, i[1] - b * yb] in dot_list:\n",
    "                return False\n",
    "        b = min(x // xb, y // yb)\n",
    "        if [x - b * xb, y - b *yb] in dot_list:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xi=0\n",
    "        yi=0\n",
    "        first_coor = [[0,0]]\n",
    "        for c in command:\n",
    "            if c == 'R':\n",
    "                xi+=1\n",
    "            else:\n",
    "                yi+=1\n",
    "            first_coor.append([xi,yi])\n",
    "        circle = min(x//xi,y//yi)\n",
    "        if [x-xi*circle,y-yi*circle] not in first_coor:\n",
    "            return False\n",
    "        for ob in obstacles:\n",
    "            ob_x,ob_y = ob[0],ob[1]\n",
    "            circle =  min(ob_x//xi,ob_y//yi)\n",
    "            if ob_x<=x and ob_y<=y and [ob_x - xi*circle,ob_y-yi*circle] in first_coor:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], A: int, B: int) -> bool:\n",
    "        x = y = 0\n",
    "        tmp = []\n",
    "        for i,j in obstacles:\n",
    "            tmp.append(i*10**10 + j)\n",
    "        s = set(tmp)\n",
    "\n",
    "        while True:\n",
    "            for i in command:\n",
    "                if i == 'U':\n",
    "                    y+=1\n",
    "                else:\n",
    "                    x+=1\n",
    "\n",
    "                if x*10**10 + y in s:\n",
    "                    return False\n",
    "                if x > A and y > B:\n",
    "                    return False\n",
    "                if x == A and y == B:\n",
    "                    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        n=x+y\n",
    "        m=len(command)\n",
    "        a=[0]*(m+1)\n",
    "        for i in range(m):\n",
    "            if command[i] == 'R':\n",
    "                a[i+1]=a[i]+1\n",
    "            else:\n",
    "                a[i+1]=a[i]\n",
    "        \n",
    "        for ob in obstacles:\n",
    "            t = ob[0]+ob[1]\n",
    "            if t < n:\n",
    "                t1 = t % m\n",
    "                t2 = t // m\n",
    "                ob[0] -= t2*a[-1]\n",
    "                if a[t1] == ob[0]:\n",
    "                    return False\n",
    "        \n",
    "        t1 = n % m\n",
    "        t2 = n // m\n",
    "        x -= t2*a[-1]\n",
    "        if a[t1] == x:\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import time\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "        time.sleep(0.5)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xx, yy = 0, 0\n",
    "        dot_list = [[0, 0]]\n",
    "        for i in command:\n",
    "            if i == 'R':\n",
    "                xx += 1\n",
    "            else:\n",
    "                yy += 1\n",
    "            dot_list.append([xx, yy])\n",
    "        xb = dot_list[-1][0]\n",
    "        yb = dot_list[-1][1]\n",
    "        for i in obstacles:\n",
    "            if i[0] > x or i[1] >y:\n",
    "                continue\n",
    "            b = min(i[0] // xb, i[1] // yb)\n",
    "            if [i[0] - b * xb, i[1] - b * yb] in dot_list:\n",
    "                return False\n",
    "        b = min(x // xb, y // yb)\n",
    "        if [x - b * xb, y - b *yb] in dot_list:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xi =yi= 0\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [(0, 0)]\n",
    "        for c in command:\n",
    "            if c == 'R' :xi += 1\n",
    "            else:yi += 1\n",
    "            first_coor.append((xi, yi))\n",
    "        first_coor=set(first_coor)\n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "        if (x-xi * circle, y-yi * circle) not in first_coor:return False\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for ax, ay  in obstacles:\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ax // xi, ay// yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ax <= x and ay <= y and (ax - xi * circle, ay - yi * circle) in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n",
    "'''\n",
    "作者：dongmen\n",
    "链接：https://leetcode.cn/problems/programmable-robot/solutions/55299/python-chang-gui-jie-fa-jian-dan-yi-dong-by-dong-m/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [(0, 0)]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append((xi, yi))\n",
    "        first_coor=set(first_coor)\n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if (x-xi * circle, y-yi * circle) not in first_coor:return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for ob_x, ob_y  in obstacles:\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and (ob_x - xi * circle, ob_y - yi * circle) in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n",
    "'''\n",
    "作者：dongmen\n",
    "链接：https://leetcode.cn/problems/programmable-robot/solutions/55299/python-chang-gui-jie-fa-jian-dan-yi-dong-by-dong-m/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import time\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "        time.sleep(0.2)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        move = [0,0]\n",
    "\n",
    "        for i in command:\n",
    "            if i == \"U\":\n",
    "                move[1] += 1\n",
    "            else:\n",
    "                move[0] += 1\n",
    "        \n",
    "        \n",
    "        zhangai = []\n",
    "        for i in range(len(obstacles)):\n",
    "            if obstacles[i][0] >x or obstacles[i][1] >y:\n",
    "                continue\n",
    "            chu = min(obstacles[i][0]//move[0],obstacles[i][1]//move[1])\n",
    "            zhangai.append([obstacles[i][0]-chu*move[0],\n",
    "                            obstacles[i][1]-chu*move[1]])\n",
    "        chu = min(x//move[0],y//move[1])\n",
    "        x =x-chu*move[0]\n",
    "        y = y-chu*move[1]\n",
    "        \n",
    "        move = [0,0]\n",
    "        flag = False\n",
    "        if move == [x,y]:\n",
    "            flag = True\n",
    "        if move in zhangai:\n",
    "            return False \n",
    "        \n",
    "        for i in command:\n",
    "            if i == \"U\":\n",
    "                move[1] += 1\n",
    "            else:\n",
    "                move[0] += 1\n",
    "            if move == [x,y]:\n",
    "                flag = True\n",
    "            if move in zhangai:\n",
    "                return False \n",
    "\n",
    "        return flag\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        sp = [(0,0)] # 索引每一步的位置\n",
    "        s = len(command) # 一个循环的步数\n",
    "        u=r=0\n",
    "        for c in command:\n",
    "            if c=='U':\n",
    "                u+=1\n",
    "            else:\n",
    "                r+=1\n",
    "            sp.append((r,u))\n",
    "        quo,rem = divmod(x+y,s)\n",
    "        # 终点是否在路径\n",
    "        if quo*r+sp[rem][0]!=x or quo*u+sp[rem][1]!=y:\n",
    "            return False\n",
    "        for i,j in obstacles:\n",
    "            if i+j>x+y: # 比终点远跳过\n",
    "                continue\n",
    "            # 障碍物是否在路径\n",
    "            quo,rem = divmod(i+j,s)\n",
    "            if quo*r+sp[rem][0]==i and quo*u+sp[rem][1]==j:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        def judge(command,xx,yy,x,y):\n",
    "            k=0\n",
    "            if xx!=0 and yy!=0:\n",
    "                k=min(x//xx,y//yy)\n",
    "            elif xx==0:\n",
    "                k=y//yy\n",
    "            elif yy==0:\n",
    "                k=x//xx\n",
    "            x-=k*xx\n",
    "            y-=k*yy\n",
    "            tempx,tempy=0,0\n",
    "            for i in range(len(command)):\n",
    "                if tempx==x and tempy==y:\n",
    "                    return True\n",
    "                if command[i]=='U':\n",
    "                    tempy+=1\n",
    "                if command[i]=='R':\n",
    "                    tempx+=1\n",
    "            return False               \n",
    "        n=len(command)\n",
    "        xx,yy=0,0\n",
    "        for i in range(n):\n",
    "            if [xx,yy] in obstacles:\n",
    "                return False\n",
    "            if xx==x and yy==y:\n",
    "                return True\n",
    "            if command[i]=='U':\n",
    "                yy+=1\n",
    "            if command[i]=='R':\n",
    "                xx+=1\n",
    "        if judge(command,xx,yy,x,y)==False:\n",
    "            return False\n",
    "        if len(obstacles)>0:\n",
    "            for j in range(len(obstacles)):\n",
    "                xxx=obstacles[j][0]\n",
    "                yyy=obstacles[j][1]\n",
    "                if xxx<=x and yyy<=y and judge(command,xx,yy,xxx,yyy)==True:\n",
    "                    return False\n",
    "            return True\n",
    "        if len(obstacles)==0:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        xi =yi= 0\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = set([(0, 0)])\n",
    "        for c in command:\n",
    "            if c == 'R' :xi += 1\n",
    "            else:yi += 1\n",
    "            first_coor.add((xi, yi))\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "        if (x-xi * circle, y-yi * circle) not in first_coor:return False\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for ax, ay  in obstacles:\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ax // xi, ay// yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ax <= x and ay <= y and (ax - xi * circle, ay - yi * circle) in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n",
    "'''\n",
    "作者：dongmen\n",
    "链接：https://leetcode.cn/problems/programmable-robot/solutions/55299/python-chang-gui-jie-fa-jian-dan-yi-dong-by-dong-m/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        right,upper = 0,0\n",
    "        one_circle = []\n",
    "        one_circle.append([0,0])\n",
    "        for i in range(len(command)):\n",
    "            if command[i] == 'U':\n",
    "                upper += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            one_circle.append([right,upper])\n",
    "        \n",
    "        circle = min(x//right,y//upper)\n",
    "        x_origin = x - right * circle\n",
    "        y_origin = y - upper * circle\n",
    "        if [x_origin,y_origin] not in one_circle:\n",
    "            return False    \n",
    "        for obstacle in obstacles:\n",
    "            if obstacle[0] <= x and obstacle[1] <= y:\n",
    "                obstacle_circle = min(obstacle[0] // right,obstacle[1] // upper)  # 任意一个障碍物最小的循环次数\n",
    "                if [obstacle[0]-right * obstacle_circle,obstacle[1] - upper * obstacle_circle] in one_circle: # 任意一个障碍物的起始点\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "\n",
    "\n",
    "        xi = 0\n",
    "        yi = 0\n",
    "\n",
    "        # 计算第一次执行完command后, 走过的所有坐标\n",
    "        first_coor = [[0, 0]]\n",
    "        for c in command:\n",
    "            if c == 'R' :\n",
    "                xi += 1\n",
    "            else:\n",
    "                yi += 1\n",
    "            first_coor.append([xi, yi])\n",
    "        \n",
    "        # 此时(xi, yi)也代表着初次command执行结束时走到的最后一个坐标\n",
    "        # 走到目标点所需要的循环次数\n",
    "        circle = min(x // xi, y // yi)\n",
    "\n",
    "        if [x - xi * circle, y - yi * circle] not in first_coor:\n",
    "            return False\n",
    "\n",
    "        # 对每个阻碍点逐个判断，是否会走到它\n",
    "        for obstacle in obstacles:\n",
    "            ob_x, ob_y = obstacle[0], obstacle[1]\n",
    "            # 走到阻碍点所需要的循环数（若是能走到的话）\n",
    "            circle = min(ob_x // xi, ob_y // yi)\n",
    "            # 判断是否会走到这个阻碍点，注意在终点之后的阻碍点可以忽略\n",
    "            if ob_x <= x and ob_y <= y and [ob_x - xi * circle, ob_y - yi * circle] in first_coor:\n",
    "                return False \n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "判断会在多少步经过某一点\n",
    "'''\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        \n",
    "        n = len(command)\n",
    "        uPre = [0] * (n + 1)\n",
    "        rPre = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            uPre[i+1] = uPre[i]\n",
    "            rPre[i+1] = rPre[i]\n",
    "\n",
    "            if command[i] == \"U\":\n",
    "                uPre[i+1] += 1\n",
    "                lastU = i\n",
    "            else:\n",
    "                rPre[i+1] += 1\n",
    "                lastR = i\n",
    "\n",
    "        def isVisit(x, y):\n",
    "            #需要达到x, 需要完整走过rdX轮，还要走resX步\n",
    "            rdX = x // rPre[-1]\n",
    "            if rdX * rPre[-1] == x:\n",
    "                #刚好完整走过\n",
    "                rdX = rdX - 1\n",
    "                resX = lastR + 1   #lastR为在command中最后出现的位置，对应rPre需要+1\n",
    "            else:    \n",
    "                resX = rPre.index(x - rdX * rPre[-1])\n",
    "\n",
    "            #需要达到y, 需要完整走过rdY轮，还要走resY步\n",
    "            udY = y // uPre[-1]\n",
    "            if udY * uPre[-1] == y:\n",
    "                udY -= 1\n",
    "                resY = lastU + 1\n",
    "            else:    \n",
    "                resY = uPre.index(y - udY * uPre[-1])\n",
    "\n",
    "            had = [(rdX, resX), (udY, resY)]\n",
    " \n",
    "            had.sort(key = lambda x : (-x[0], -x[1]))\n",
    "\n",
    "            xx = had[0][0] * rPre[-1] + rPre[had[0][1]]\n",
    "            yy = had[0][0] * uPre[-1] + uPre[had[0][1]]\n",
    "\n",
    "\n",
    "            if (xx, yy) == (x, y):\n",
    "                return had[0]\n",
    "            return False\n",
    "\n",
    "\n",
    "        tar = isVisit(x, y)\n",
    "\n",
    "        if tar == False:\n",
    "            return False\n",
    "        for x, y in obstacles:\n",
    "            temp = isVisit(x, y)\n",
    "            if temp == False:\n",
    "                continue\n",
    "            if temp <= tar:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        steps = [(0, 0)]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        us = 0\n",
    "        rs = 0\n",
    "        for c in command:\n",
    "            if c == 'U':\n",
    "                j += 1\n",
    "                us += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                rs += 1\n",
    "            steps.append((i, j))\n",
    "\n",
    "        def catch(x, y):\n",
    "            nonlocal us, rs, steps\n",
    "            n = min(x//rs, y//us)\n",
    "            x -= rs*n\n",
    "            y -= us*n\n",
    "            for i, j in steps:\n",
    "                if i == x and j == y:\n",
    "                    return True\n",
    "            return False\n",
    "        if not catch(x, y):\n",
    "            return False\n",
    "\n",
    "        obstacles.sort()\n",
    "        for ox, oy in obstacles:\n",
    "            if ox > x or oy > y:\n",
    "                break\n",
    "            if catch(ox, oy):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self, command, x_1, y_1, x, y):\n",
    "        # （x_1, y_1）是执行一遍指令第一次歇脚的位置\n",
    "\n",
    "        x_0, y_0, k = 0, 0, 0\n",
    "\n",
    "        # k 计算执行多少轮命令后即将到达终点（下一轮执行肯定能到）\n",
    "        # 使用条件判断计算 k 值，避免除以 0 的情况\n",
    "        if x_1 != 0 and y_1 != 0:\n",
    "            k = min(x // x_1, y // y_1)\n",
    "        elif x_1 == 0:\n",
    "            k = y // y_1\n",
    "        elif y_1 == 0:\n",
    "            k = x // x_1\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "            # 相当于把终点坐标拿到原点附近\n",
    "        x = x - k * x_1\n",
    "        y = y - k * y_1\n",
    "\n",
    "        # 判断下一轮是否会碰到终点\n",
    "        for i in range(len(command)):\n",
    "            if x_0 == x and y_0 == y:\n",
    "                return True\n",
    "\n",
    "            if command[i] == 'U':\n",
    "                y_0 += 1\n",
    "            else:\n",
    "                x_0 += 1\n",
    "\n",
    "        return False\n",
    "\n",
    "    def robot(self, command: str, obstacles: [[int]], x: int, y: int) -> bool:\n",
    "        n = len(command)\n",
    "        x_1 = 0\n",
    "        y_1 = 0\n",
    "        for i in range(n):\n",
    "            if command[i] == 'U':\n",
    "                y_1 += 1\n",
    "            else:\n",
    "                x_1 += 1\n",
    "        if self.helper(command, x_1, y_1, x, y)==False:\n",
    "            return False\n",
    "        for i in range(len(obstacles)):\n",
    "            x_obs = obstacles[i][0]\n",
    "            y_obs = obstacles[i][1]\n",
    "            if x_obs <= x and y_obs <= y and self.helper(command, x_1, y_1, x_obs, y_obs):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        if x== 0 and y==0:\n",
    "            return True\n",
    "        r_x = 0\n",
    "        r_y = 0\n",
    "        obstacles = set( [ tuple(i) for i in obstacles ] )\n",
    "        while True:\n",
    "            if r_x > x or r_y > y:\n",
    "                return False\n",
    "            for tmp_cmd in command:\n",
    "                if tmp_cmd == 'U':\n",
    "                    r_y += 1\n",
    "                else:\n",
    "                    r_x += 1\n",
    "                if r_x== x and r_y==y:\n",
    "                    return True\n",
    "                else:\n",
    "                    if (r_x,r_y) in obstacles:\n",
    "                        return False\n",
    "                    else:\n",
    "                        continue\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:\n",
    "        if x==0 and y==0:return True\n",
    "        \n",
    "        ori,oripos=[0,0],[]\n",
    "        for c in command:\n",
    "            if c=='U':\n",
    "                ori[1]+=1\n",
    "            else:\n",
    "                ori[0]+=1\n",
    "            oripos.append(ori[:])\n",
    "        # print(oripos[-10:])\n",
    "        divpo=oripos[-1]\n",
    "        for po in oripos: #首先检测终点坐标是否在轨迹上\n",
    "            if (x==po[0] and y==po[1]) or (y!=po[1] and (x-po[0])/(y-po[1])==divpo[0]/divpo[1]): #说明坐标(x,y)在行走轨迹上\n",
    "                break\n",
    "        else:return False #顺利遍历完毕，说明终点坐标不在轨迹上，返回false\n",
    "        \n",
    "        for ob in obstacles:\n",
    "            if ob[0]<=x and ob[1]<=y:#先保证障碍物位置在行走路径范围内，否则机器人在走到障碍物之前就先到了终点\n",
    "                for po in oripos:\n",
    "                    if (ob[0]==po[0] and ob[1]==po[1]) or (ob[1]!=po[1] and (ob[0]-po[0])/(ob[1]-po[1])==divpo[0]/divpo[1]):#说明此障碍物在行走轨迹上，返回true\n",
    "                        return False\n",
    "        else:return True #顺利遍历完毕，说明到达终点前没有障碍物在轨迹上，返回true\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
